//
// Description: 字符串哈希模板
// Created by Loading on 2021/7/29.
//

/*
 * 核心思想：将字符串看成P进制数，P的经验值是 131 或 13331，取这两个值的冲突概率低
 * 小技巧：取模的数用2^64，这样直接用unsigned long long存储，自然溢出，溢出的结果就是取模的结果
 */

// 例题：5803.最长公共子路径

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

const int N = 100001;
/* 哈希经验值，存在哈希冲突时可调整 */
const int P = 13331;
// 哈希数组
// h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
uLL h[N], p[N];

// 初始化哈希数组
void init(string str, int len) {
    p[0] = 1;
    for (int i = 1; i <= len; ++i) {
        h[i] = h[i - 1] * P + str[i - 1];
        p[i] = p[i - 1] * P;
    }
}

// 得到子串 str[l ~ r] 的哈希值，范围：第 l 个到第 r 个，包含 l 和 r
uLL getHash(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {

}